package com.cjm.algorithm.babo;

import com.cjm.algorithm.GeneratorUtils;
import com.cjm.algorithm.HelpUtils;

import java.util.Arrays;

public class MergeSort {
    private static void doMerge(int[] arr, int l, int mid, int r) {
        int[] aux = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1;
        for(int k = l;k<=r;k++) {
            if (i>mid) {
                arr[k] = aux[j-l];j++;
            }else if (j > r) {
                arr[k] = aux[i-l];i++;
            }else if( aux[i - l] < aux[j - l]) {
                arr[k] = aux[i-l];i++;
            } else {
                arr[k] = aux[j-l];j++;
            }
        }
    }
    private static void sort(int[] arr, int l, int r) {
        if (l>=r) {
            return;
        }
        int mid = (r - l)/2 + l;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);

        doMerge(arr, l, mid, r);
    }



    private static void sort(int[] arr) {
        if (arr == null || arr.length < 1) {
            return;
        }

        int len = arr.length -1;
        sort(arr, 0, len);
    }



    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            int[] generator = GeneratorUtils.generator(50, 0, 50);
            sort(generator);
            GeneratorUtils.print(generator);        }
    }
}
